With the field of compilers, the problem of handling exceptions is important for languages that permit them. For example, the C++ and JAVA programming language permit a program to “throw an exception”, which means that a structure (the exception) is constructed, and then transmitted (thrown) up the execution stack until a handler catches the exception, at which point normal execution continues. A key feature of both C++ and JAVA programming language is that they permit the programmer to specify cleanup actions to be performed if an exception is thrown. In C++, these actions are destructions of objects that are popped from the execution stack by the throwing of the exception. In JAVA programming language, these actions are code specified by “finally” clauses.
There are a variety of ways of keeping track of cleanup actions. One way is to construct lookup tables that are consulted when an exception is thrown. The tables map program-counter values onto cleanup actions, so that when an exception is thrown, the exception-handling mechanism can, knowing the current program-counter value, determine the necessary cleanup actions. The disadvantage of this prior-art technique is that the tables require expressing program-counter values and offsets within the execution stack, a notion not directly expressible in the C language, and thus is not amenable to implementation in compilers that generate intermediate code in the C language.
Another approach is, during normal execution, to register each cleanup action by pushing it onto a “exception-handling (EH) stack” when it might be needed to handle an exception, and popping it from said stack when it is no longer needed. This prior-art approach has the advantage that it is amenable to compilers that generate intermediate code in the C language. However, prior-art implementations have the disadvantage of being quite inefficient, because of excessive pushing and popping of the EH stack.
FIG. 1 shows an example program in the C++ language. It declares types S and T. Declaration 100 declares type S to have constructor 101 and destructor 102, both of which have throw( ) clauses that specify that they cannot throw exceptions. Declaration 103 declares type T to have constructor 104 and destructor 105, both of which can throw an exception since neither contains a throw( ) clause. Declaration 106 declares routine “woof”, which may throw an exception if called. Declaration 107 constructs an object “ant”. A try block (between braces 108 and 116) surrounds the if-statement with test 109. If x>0, then declaration 110 constructs object “boa”. There is an implicit call to the destructor ˜S for boa at brace 111, because the scope in which “boa” was declared is exited. If x≦0, then declarations 112 and 113 construct objects “cat” and “dog” respectively, followed by call 114 to “woof”. At brace 115, objects “dog” and “cat” are destroyed by implicit calls to their destructors, because their scope is being exited. Destructions are always in reverse order of construction. If an exception is thrown while execution is inside the try block, then any objects constructed inside the try block (i.e. between brace 108 and brace 116) are destroyed, and then the catch handler is inspected to see if it matches the type of exception thrown, which in this case is thrown objects of type int. If the handler matches, the block between braces 117 and 119 is executed. Declaration 118 constructs object “elk”. There is an implicit call to the destructor ˜S at brace 120 to destroy “elk” if the handler is exited by normal execution or because call 119 to “woof” throws an exception. Object “ant” is destroyed when the outer block (ending at brace 121) is exited, no matter whether the exit is by normal execution or because an uncaught exception was thrown.
Actions taken between the time an exception is thrown and a matching try block is found are called “cleanup”.
FIG. 2 shows the basic declarations for an example EH stack. The stack consists of zero or more instances of structure 200 EH_item, each of which is part of a linked list linked by field 201 “next” that points to the next EH_item deeper in the stack. The top of the stack is represented by global variable 207 EH_stack_ptr, which points to the root of the linked list. Tag 202 indicates the kind of item. There are two kinds of items in the example: items that specify destructions of objects, and items that specify try blocks.
For the destruction of an item, the tag is DESTROY. Field 203 “object” points to the object to be destroyed, and field 204 “dtor” points to the code to invoke for that item. For other sorts of cleanup, say the JAVA programming language “finally” clause, or C++“exception specifications”, the field “dtor” points to the code to be executed, and the “object” field is not used, or points to some sort of data structure that further specifies the cleanup to be done. (The exact nature of the cleanup is beyond the scope of this disclosure, and therefore the cleanups in the example are restricted to simple destructions.)
For try blocks, the tag is TRY, and field 205 “buffer” contains information required to resume normal execution if the handler catches an exception. The field 206 handlers point to information about the type of exceptions caught, and their respective handlers. (The exact nature of the handlers is also beyond the scope of this disclosure. Those skilled in the art will appreciate that for a try block, there is information related to how to resume normal execution, and information related to determining the type of exception caught.)
FIG. 3 shows a translation of FIG. 1 using the prior art. Calls to constructors and destructors are explicit in the translation. Lines 303 and 344 respectively call the constructor and destructor for object “ant”. Each time an object is constructed, an EH_item for the object is pushed onto the EH stack by adding it to the front of the linked list rooted at EH_stack_ptr. Items “ra”, “rb”, “rc”, “rd”, “re”, and “rt” correspond to objects ant, boa, cat, dog, elk, and the try block respectively. The requisite fields of each EH_item are set immediately after the corresponding object is constructed. For example, line 313 constructs object “boa”, and lines 313–317 set “rb” and push it on the EH stack. When execution is about to exit a block, before each object to be destroyed is destroyed, the corresponding item on the EH stack is popped by removing it from the linked list. For example, line 317 pops “rb” from the EH stack.
The code in FIG. 3 is inefficient because it fills fields prematurely. For example, call 311 to “setjmp” fills in information that is used only if an exception is thrown, but if x>0, then only object “boa” is constructed, and both the constructor and destructor for boa were declared as never throwing an exception. Similarly, despite the fact that the constructor and destructor for “ant” can both throw exceptions, if x>0, there is nothing between the call to the constructor and destructor for “ant” that might require the exceptional destruction of ant. Thus, setting EH_item “ra” and pushing it on the EH stack (lines 304–306) for sake of “ant”, and setting EH_item “rt” and pushing it on the EH_stack (lines 307–310) for sake of the try block are unnecessary when x>0. Likewise, EH item “rb” is in fact useless, and lines 314–317 contribute nothing but inefficiency. Furthermore, lines 342–343 pop two EH_items from the EH stack less than perfectly: the same effect could have been achieved more quickly via “EH_stack_ptr=ra.next”.
A common method of removing inefficiencies is partial redundancy elimination. Unfortunately, prior-art methods of partial redundancy analysis do not handle redundancies as complicated as adding or removing items from a linked list. What is needed is an approach that circumvents the problem by analyzing programs in a way that generates a problem more amenable to partial redundancy elimination.